#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define int long long
typedef long long LL;



signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

//void solve() {
//	int n, m;
//	cin >> n >> m;
//	vector<string> grid1, grid2;
//	for (int i = 0; i < n; i++) {
//		string s;
//		cin >> s;
//		grid1.push_back(s);
//	}
//	for (int i = 0; i < n; i++) {
//		string s;
//		cin >> s;
//		grid2.push_back(s);
//	}
//	vector<int> sc1(m), sc2(m), sr1(n), sr2(n);
//	for (int i = 0; i < n; i++) {
//		for (int j = 0; j < m; j++) {
//			sr1[i] += (grid1[i][j] - '0');
//			sr1[i] %= 3;
//			sr2[i] += (grid2[i][j] - '0');
//			sr2[i] %= 3;
//			sc1[j] += (grid1[i][j] - '0');
//			sc1[j] %= 3;
//			sc2[j] += (grid2[i][j] - '0');
//			sc2[j] %= 3;
//		}
//	}
//	bool ok = 1;
//	for (int i = 0; i < n; i++) {
//		ok &= (sr1[i] == sr2[i]);
//	}
//	for (int i = 0; i < m; i++) {
//		ok &= (sc2[i] == sc1[i]);
//	}
//	if (ok)cout << "YES\n";
//	else cout << "NO\n";
//}
//

//
//void solve() {
//	int n, L, R;
//	cin >> n >> L >> R;
//	int sum = 0;
//	int ans = 0;
//	vector<int> a(n + 1);
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//	}
//	for (int l = 1, r = 1; l <= n;) {
//		while (sum < L && r <= n) {
//			sum += a[r];
//			r++;
//		}
//		if (sum <= R && sum >= L) {
//			ans++;
//			sum = 0;
//			l = r;
//		}
//		else {
//			sum -= a[l];
//			l++;
//		}
//	}
//	cout << ans << '\n';
//}

//void solve() {
//	int n, L, R;
//	cin >> n >> L >> R;
//	vector<int> a(n + 1);
//	vector<int> sum(n + 1);
//	vector<int> dp(n + 1);
//	int ans = 0;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//		sum[i] = sum[i - 1] + a[i];
//	}
//	for (int i = 1; i <= n; i++) {
//		dp[i] = dp[i - 1];
//		int l = 0, r = i, m;
//		while (l < r) {
//			m = (l + r + 1) >> 1;
//			if (sum[i] - sum[m - 1] >= L) {
//				l = m;
//			}
//			else {
//				r = m - 1;
//			}
//		}
//		if (l != 0 && sum[i] - sum[l - 1] >= L && sum[i] - sum[l - 1] <= R)
//			dp[i] = dp[l - 1] + 1;
//	}
//	cout << dp[n] << '\n';
//}


//void solve() {
//	int x, y, k;
//	cin >> x >> y >> k;
//	int need = 0;
//	while (k) {
//		need = y - (x % y);
//		if (k < need) {
//			x += k;
//			break;
//		}
//		k -= need;
//		x += need;
//		while (x % y == 0) {
//			x /= y;
//		}
//		if (x == 1) {
//			k %= (y - 1);
//			x += k;
//			break;
//		}
//	}
//
//	cout << x << '\n';
//}

//void solve() {
//	int n, m;
//	cin >> n >> m;
//	int ans = 0;
//	for (int i = 0; i <= 30; i++) {
//		int x = n & ((1LL << (i + 1)) - 1);
//		if (x >= (1LL << i)) {
//			ans |= (1LL << i);
//			continue;
//		}
//		int t = (1LL << i) - x;
//		if (n >= (1LL << i)) {
//			t = min(t, x + 1);
//		}
//		if (t <= m) {
//			ans |= (1LL << i);
//		}
//	}
//	cout << ans << '\n';
//}
//


//void solve() {
//	int n, m;
//	cin >> n >> m;
//	int ans = 0;
//	for (int i = 0; i <= 30; ++i) {
//		int x = n & ((1LL << (i + 1)) - 1);
//		int t = (1LL << i) - x;
//		if (n >= (1LL << i)) {
//			t = min(t, x + 1);
//		}
//		if (x >= (1LL << i) || t <= m) {
//			ans |= (1LL << i);
//		}
//	}
//	printf("%lld\n", ans);
//}


//int gcd(int x, int y) {
//	return y ? gcd(y, x % y) : x;
//}
//
//bool check(vector<int>& x) {
//	int cur = -1;
//	int pre = -1;
//	for (int i = 1; i < x.size() - 1; i++) {
//		cur = gcd(x[i], x[i + 1]);
//		if (pre > cur) {
//			return false;
//		}
//		pre = cur;
//	}
//	return true;
//}
//
//void solve() {
//	int n;
//	cin >> n;
//	int pre = -1;
//	int cur = -1;
//	int to = -1;
//	vector<int> a(n + 1);
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//	}
//	for (int i = 1; i <= n - 1; i++) {
//		cur = gcd(a[i], a[i + 1]);
//		if (pre > cur) {
//			to = i;
//			break;
//		}
//		pre = cur;
//	}
//	if (to == -1) {
//		cout << "YES\n";
//		return;
//	}
//	vector<int> b0(a), b1(a), b2(a);
//	if (to > 1) b0.erase(b0.begin() + to - 1);
//	b1.erase(b1.begin() + to);
//	if (to < n)b2.erase(b2.begin() + to + 1);
//	if (check(b1) || check(b2) || check(b0)) {
//		cout << "YES\n";
//	}
//	else {
//		cout << "NO\n";
//	}
//}



//int a[200005];
//int b[200005];
//int d[200005];
//
//
//void solve() {
//	int n;
//	cin >> n;
//	map<int, int> ma;
//	map<int, vector<int>>index;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//		ma[a[i]]++;
//	}
//	map<int, int> need;
//	for (int i = 1; i <= n; i++) {
//		cin >> b[i];
//		if (b[i] != a[i])
//			need[b[i]]++;
//	}
//	int m;
//	cin >> m;
//	for (int i = 1; i <= m; i++) {
//		cin >> d[i];
//		if (need.count(d[i])) {
//			need[d[i]]--;
//			if (need[d[i]] == 0)
//				need.erase(d[i]);
//		}
//	}
//	int f = 0;
//	for (int i = 1; i <= n; i++) {
//		if (b[i] == d[m]) {
//			f = 1;
//		}
//	}
//	if (!f||!need.empty()) {
//		cout << "NO\n";
//		return;
//	}
//	cout << "YES\n";
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int t;
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//
//	return 0;
//}

//int a[200005];
//int r[200005];
//
//void solve() {
//	int n, m;
//	cin >> n >> m;
//	map<int, int> mp;
//
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//	}
//
//	for (int i = 1; i <= n; i++) {
//		cin >> r[i];
//	}
//
//	for (int i = 1; i <= n; i++) {
//		int now = a[i];
//		int h = r[i];
//		if (h > mp[now])
//			mp[now] = h;
//		for (int j = 1; j <= r[i] && h; j++) {
//			while (j * j + h * h > r[i] * r[i]) {
//				h--;
//			}
//			if (h > mp[a[i] + j]) {
//				mp[a[i] + j] = h;
//			}
//			if (h > mp[a[i] - j]) {
//				mp[a[i] - j] = h;
//			}
//		}
//	}
//	int ans = mp.size();
//	for (auto x : mp) {
//		ans += x.second * 2;
//	}
//	cout << ans << '\n';
//}